package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class LongestSubstringWithoutRepeatingCharacters {

  public static void main(String[] args) {
    Solution solution = new LongestSubstringWithoutRepeatingCharacters().new Solution();
    // put your test code here


    System.out.println(solution.lengthOfLongestSubstring("abcabcbb"));

  }
  // leetcode submit region end(Prohibit modification and deletion)

  // leetcode submit region begin(Prohibit modification and deletion)
  class Solution {
    public int lengthOfLongestSubstring(String s) {
      // 找到最长的不重复字串

      int maxLength = 0;
      final HashMap<Character, Integer> existsMap = new HashMap<>();

      int left = 0;
      int right = 0;
      // 右侧先动
      while (right < s.length()) {
        final char c = s.charAt(right);

        // 窗口更新
        existsMap.put(c, existsMap.getOrDefault(c, 0) + 1);

        right++;

        // 看左侧是否需要收缩
        while (existsMap.get(c) > 1) {
          final char leftChar = s.charAt(left);
          left++;
          existsMap.put(leftChar, existsMap.get(leftChar) - 1);
        }

        // 更新最大值
        maxLength = Math.max(maxLength, right - left);
      }
      return maxLength;
    }
  }
}
